package com.hy.study.algorithm.dijkstra;

import java.util.Arrays;

/**
 * 狄杰斯特拉算法
 */
public class DijkstraAlgorithm {
    private static final int INF = 65535;

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {
                {
                        INF, 5, 7, INF, INF, INF, 2
                },
                {
                        5, INF, INF, 9, INF, INF, 3
                },
                {
                        7, INF, INF, INF, 8, INF, INF
                },
                {
                        INF, 9, INF, INF, INF, 4, INF
                },
                {
                        INF, INF, 8, INF, INF, 5, 4
                },
                {
                        INF, INF, INF, 4, 5, INF, 6
                },
                {
                        2, 3, INF, INF, 4, 6, INF
                }

        };

        Graph graph = new Graph(vertex, matrix);
        graph.showGraph();
        graph.dsj(6);
        graph.showDijGraph();

    }
}

class Graph {
    private char[] verrtex;//顶点数组
    private int[][] matrix;//邻接矩阵
    private VisitedVertex visitedVertex;//已经访问顶点的集合

    public Graph(char[] verrtex, int[][] matrix) {
        this.verrtex = verrtex;
        this.matrix = matrix;
    }

    public void showGraph() {
        for (int[] link : matrix) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 迪杰斯特拉算法实现
     */
    public void dsj(int index) {
        visitedVertex = new VisitedVertex(verrtex.length, index);
        update(index);//更新下标为index 节点到周围顶点的距离和前驱节点
        for (int i = 1; i < verrtex.length; i++) {
            //选择并返回下一个访问节点得到下标
            index = visitedVertex.updateArr();
            update(index);
        }
    }

    //更新index 下标顶点到周围顶点的距离和周围顶点的前驱顶点
    private void update(int index) {
        int len = 0;
        for (int i = 0; i < matrix[index].length; i++) {
            //已经访问过的距离+ 从index 顶点到i节点的距离之和
            len = visitedVertex.getDis(index) + matrix[index][i];
            //如果i 节点没有被访问过 并且 i 小于 出发顶点 小于到j 距离
            if (!visitedVertex.in(i) && len < visitedVertex.getDis(i)) {
                visitedVertex.updatePre(i, index);//更新i 节点的前驱节点为index 节点
                visitedVertex.updateDis(i, len);//更新出发节点到i节点的距离
            }
        }
    }

    //显示最后结果
    public void showDijGraph() {
        this.visitedVertex.show();
    }

}

/**
 * 已经访问顶点集合
 */
class VisitedVertex {
    /**
     * 记录各个顶点是否被访问过 1表示访问过 0 表示未访问，会动态更新
     */
    public int[] already_arr;
    /**
     * 每个下标对应的值未前一个顶点下标，会动态更新
     */
    public int[] pre_visited;
    /**
     * 记录出发订单到其他所有顶点的距离，如果G为出发点，就会记录G到其他顶点的距离，会动态更高兴，就的最短距离就会存放在dis
     */
    public int[] dis;

    /**
     * 构造器
     *
     * @param length 表示顶点个数
     * @param index  出发顶点对应的下标
     */
    public VisitedVertex(int length, int index) {
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        //初始化dis 数组
        Arrays.fill(dis, 65535);
        //自己与自己 设置为0 出发节点访问路径距离
        this.dis[index] = 0;
        //设置出发节点为已访问
        this.already_arr[index] = 1;
    }

    /**
     * 判断 index 对应的节点是否被访问过
     *
     * @param index 节点下标
     * @return 如果访问过返回true 否则返回false
     */
    public boolean in(int index) {
        return already_arr[index] == 1;
    }

    /**
     * 更新出发顶点到index 顶点的距离
     *
     * @param index
     * @param len
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 更新pre顶点的前驱为index节点
     *
     * @param pre
     * @param index
     */
    public void updatePre(int pre, int index) {
        pre_visited[pre] = index;
    }

    /**
     * 返回出发顶点到index 顶点的距离
     *
     * @param index
     */
    public int getDis(int index) {
        return dis[index];
    }

    /**
     * 继续选择并返回新的访问节点，比如这里的G完后 i，就是A点作为新年的访问节点
     *
     * @return
     */
    public int updateArr() {
        int min = 65535;
        int index = 0;
        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i] == 0 && dis[i] < min) {//没有被访问过
                min = dis[i];
                index = i;
            }
        }
        //更新index 节点被访问过
        already_arr[index] = 1;
        return index;
    }

    /**
     * 显示最后结果
     */
    public void show() {
        System.out.println("============");
        for (int i : already_arr) {
            System.out.print(i + "\t");
        }
        System.out.println();

        //输出前驱节点
        for (int i : pre_visited) {
            System.out.print(i + "\t");
        }
        System.out.println();

        //输出dis
        for (int i : dis) {
            System.out.print(i + "\t");
        }
        System.out.println();
        //为了好看处理下节点
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "(" + i + ")");
            } else {
                System.out.print("INF");
            }
            count++;
        }
    }
}
